package baseclass.f_hash;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 并查集:
 * 并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作。
 * 不过需要注意并查集虽然可以进行合并操作，但是却无法进行分割操作。
 *
 * @date 2020/2/29 16:39
 */
class Node {
    // whatever you like,string,char,int .....obj
}

public class Code03_UnionFind {
    //K是Node，V是Node所属的并查集的代表节点---父节点
    private Map<Node, Node> fatherMap;
    //K是并查集的代表节点，V是并查集大小
    private Map<Node, Integer> sizeMap;

    public Code03_UnionFind() {
        fatherMap = new HashMap<>();
        sizeMap = new HashMap<>();
    }

    public Code03_UnionFind(List<Node> nodes) {
        this();
        for (Node node : nodes) {
            //一开始每个节点属于独立的并查集
            fatherMap.put(node, node);
            sizeMap.put(node, 1);
        }
    }

    /**
     * 查找集合的代表节点。
     * 做了优化，当前节点到代表节点的所有节点都直接指向代表节点.
     * 每次访问节点i，则从i到其代表节点（父节点）的所有元素都进行路径压缩，
     * 把这一路上的所有节点都直接指向代表节点。
     */
    private Node findFatherHead(Node node) {
        Node fatherNode = fatherMap.get(node);
        if (node != fatherNode) {
            fatherNode = findFatherHead(fatherNode);
        }
        //node = fatherNode，找到了顶层。回溯后每个node都put最顶层的fatherNode
        fatherMap.put(node, fatherNode);
        return fatherNode;
    }

    public boolean isSameSet(Node a, Node b) {
        return findFatherHead(a) == findFatherHead(b);
    }

    public void union(Node a, Node b) {
        if (a == null || b == null) return;
        Node fatherA = findFatherHead(a);
        Node fatherB = findFatherHead(b);
        if (fatherA != fatherB) {
            int size1 = sizeMap.get(fatherA);
            int size2 = sizeMap.get(fatherB);
            //把B的所有节点挂到A下面
            if (size1 > size2) {
                fatherMap.put(fatherB, fatherA);
                sizeMap.put(fatherA, size1 + size2);
            }else {
                fatherMap.put(fatherA, fatherB);
                sizeMap.put(fatherB, size1 + size2);
            }
        }

    }
}
